package fun.ticsmyc.sort;

import fun.ticsmyc.tools.ArrayTools;
import org.junit.Test;

import java.util.Arrays;

/**
 * 二路归并
 *
 * @author Ticsmyc
 * @package fun.ticsmyc.sort1
 * @date 2020-01-30 17:44
 */
public class MergeSort {

    public static void mergeSort(int[] arr){
        if(arr==null || arr.length <=1){
            return ;
        }
        sort(arr,0,arr.length-1);
    }

    /**
     * 从arr[head] 到 arr[tail]
     * @param arr
     * @param head
     * @param tail
     */
    public static void sort(int[] arr, int head,int tail){
        if(head == tail){
            return;
        }
        int mid = (head+tail)/2;
        sort(arr,head,mid);
        sort(arr,mid+1,tail);
        merge(arr,head,tail);
    }

    /**
     * 从arr[head]到arr[tail]
     * @param arr
     * @param head
     * @param tail
     */
    public static void merge(int[] arr, int head,int tail){
        int mid = (head+tail)/2;
        int leftBegin = head;
        int rightBegin=mid+1;
        int length = tail-head+1;
        int[] temp=new int[length];
        int tempIndex=0;
        while(leftBegin<=mid && rightBegin<=tail){
            if(arr[leftBegin]<arr[rightBegin]){
                temp[tempIndex++]=arr[leftBegin++];
            }else{
                temp[tempIndex++]=arr[rightBegin++];
            }
        }
        while(leftBegin<=mid){
            temp[tempIndex++]=arr[leftBegin++];
        }
        while(rightBegin<=tail){
            temp[tempIndex++]=arr[rightBegin++];
        }
        for(int i=0 ; i<tempIndex;++i){
            arr[head+i] = temp[i];
        }
    }

    @Test
        public void test(){
        //测试次数
        int testTime=5_000_000;
        //数组大小
        int size=10;
        //数组值 -100 ~ +100
        int value=100;
        boolean succeed =true;

        for(int i=0;i<testTime;++i){
            int[] arr1 = ArrayTools.generateRandomArray(size,value);
            int[] arr2 = Arrays.copyOf(arr1,arr1.length);
            int[] arr3 = Arrays.copyOf(arr1,arr1.length);

            mergeSort(arr1);
            ArrayTools.rightSortMethod(arr2);
            if(!Arrays.equals(arr1,arr2)){
                succeed=false;
                //打印原数组
                ArrayTools.printArray(arr3);
                break;
            }
        }
        System.out.println( succeed ? "nice" : "Fucking fucked!");
    }

    @Test
    public void testOne(){
        int[] arr1 =new int[]{-82,32  ,-3 , -17 , -14 , 43  ,71,  40 , 35 , 24 };
        ArrayTools.printArray(arr1);
        mergeSort(arr1);
        ArrayTools.printArray(arr1);
    }

}
